package org.jspar.place;

import java.util.ArrayList;
import java.util.List;

import org.jspar.tile.ITileContent;
import org.jspar.tile.Position;
import org.jspar.tile.Tile;

public class TileOperations {
	
	private static final int FURTHER = 0;
	private static final int CLOSER = 1;

	public static Tile angledTileInsertion(Tile currentTile, Position anchor, SideSelector selector,
			Position pivot, int width, int height, ITileContent box) {
		if (selector.hasNoSide())
			return null;
		Tile new_ = null;
		int tx = 0;
		int ty = 0;
		List<Tile> lineList = findAllTilesAlongLine(currentTile, anchor, selector, new ArrayList<Tile>());
		Tile cornerTile = firstNoncontiguousFullTile(lineList);
		int newAnchX = anchor.x();
		int newAnchY = anchor.y();
		while (lineList.size() > 0) {
			new_ = angledTileHelp(currentTile, newAnchX, newAnchY, selector,
					pivot, width, height, box, cornerTile);

			if (new_ != null)
				break;

			/* reset the anchor-point and <cornerTile> and try again */
			/*
			 * The new anchor point is some point in the current cornerTile that
			 * lies along the axis of motion:
			 */
			if (selector.xSideCount != 0) {
				ty = (int) ((float) selector.ySideCount
						/ (float) selector.xSideCount * (cornerTile.x() - newAnchX))
						+ newAnchY;
			}
			if (selector.ySideCount != 0) {
				tx = (int) ((float) selector.xSideCount
						/ (float) selector.ySideCount * (cornerTile.x() - newAnchY))
						+ newAnchX;
			}
			if (ty >= cornerTile.y() && ty <= cornerTile.bottom())
				newAnchY = ty;
			else
				newAnchY = cornerTile.y();

			if (tx >= cornerTile.x() && tx <= cornerTile.right())
				newAnchX = tx;
			else
				newAnchY = cornerTile.x();

			cornerTile = firstNoncontiguousFullTile(lineList);
		}
		if (new_ == null)
			new_ = angledTileHelp(currentTile, newAnchX, newAnchY, selector,
					pivot, width, height, box, cornerTile);

		if (new_ == null)
			throw new RuntimeException("angled_tile_insertion: Complete Failure");

		return new_;
	}
	
	private static List<Tile> findAllTilesAlongLine(Tile currentTile, Position anchor,
			SideSelector selector, List<Tile> soFar) {
		Tile neighbor;
		int delX = selector.xSideCount;
		int delY = selector.ySideCount;
		int x, y, xx = 0, yy = 0; /*
								 * point on <temp>'s far edge that lies on the
								 * line
								 */
		int bx, by;
		boolean yset = false, xset = false;
		int nextX = 0, nextY = 0;

		Tile temp = currentTile.locate(anchor);
		if (temp == null)
			return soFar;

		 /* <srcX> and <srcY> are in <start> */
		if (temp == currentTile) {
			/* Recursion Stop?? */
			if (temp.x() == anchor.x() || temp.right() == anchor.x()) {
				return soFar;
			}

			if (temp.y() == anchor.y() || temp.bottom() == anchor.y()) {
				return soFar;
			}
			// throw new RuntimeException(
			// "find_all_tiles_along_line: Problem, am totally lost!");
		}

		/*
		 * Due to the strageness introduced by adding all tiles around a corner
		 * that lies on a line, check to see if this tile is on the list
		 * already, so he isn't added twice. Note that this means that only the
		 * last two entries on the list need be checked. If <temp> is not on
		 * <soFar>, then add him. If so, don't add him.
		 */
		if (!soFar.contains(temp))
			soFar.add(temp);
		// for (tl = soFar; ((tl != null) && (tl.next != null) &&
		// (tl.next.next == null)); tl = tl.next);

		/* Now at or near the end of <soFar> */
		// if (tl == null)
		// soFar.add(temp); /* list_length(*soFar) = 0 */
		// else if (tl.next != null && tl.this_ != temp && tl.next.this_ !=
		// temp)
		// soFar.add(temp); /* list_length(*soFar) = 2 */
		// else if (tl.this != temp && tl.next == null)
		// soFar.add(temp); /* list_length(*soFar) = 1*/
		/* Find the points where the line intersects the edge of the tile: */
		if (delX != 0) {
			xx = (delX < 0) ? temp.x() : temp.right();
			by = (anchor.y() - (int) ((float) delY / (float) delX * (float) anchor.x()));
			y = (int) ((float) delY / (float) delX * (float) xx) + by;
			nextY = (int) ((float) delY / (float) delX * ((float) xx + (float) delX
					/ Math.abs(delX)))
					+ by;
			if (y <= temp.bottom() && y >= temp.y())
				yset = true;
		}
		if (delY != 0) {
			yy = (delY < 0) ? temp.y() : temp.bottom();
			bx = (anchor.x() - (int) ((float) delX / (float) delY * (float) anchor
					.y()));
			x = (int) ((float) delX / (float) delY * (float) yy) + bx;
			nextX = (int) ((float) delX / (float) delY * ((float) yy + (float) delY
					/ Math.abs(delY)))
					+ bx;
			if (x <= temp.right() && x >= temp.x())
				xset = true;
		}

		/* now that these calculations are done, locate the edge intersection: */
		if (yset && xset) /* The point is a corner @ (x,y) */
		{
			y = yy; /* This causes other problems */
			x = xx;
			if (delY > 0) /* Upper... */
			{
				if (delX > 0) /* Right-Hand Corner */
				{
					/*
					 * nextX = x + 1; Might be needed.... nextY = y + 1;
					 */
					if (temp.topRight() != null)
						soFar.add(temp.topRight());
					if (temp.rightTop() != null)
						soFar.add(temp.rightTop());
				} else /* Left Hand Corner */
				{
					neighbor = temp.locate(new Position(x - 1, y + 1));
					if (neighbor != null)
						soFar.add(neighbor);
					/* tiles might get on <soFar>2x */
					neighbor = temp.locate(new Position(x - 1, y - 1));
					if (neighbor != null)
						soFar.add(neighbor);
				}
			} else /* Lower... */
			{
				if (delX > 0) /* Right-Hand Corner */
				{
					neighbor = temp.locate(new Position(x + 1, y - 1));
					if (neighbor != null)
						soFar.add(neighbor);
					neighbor = temp.locate(new Position(x - 1, y - 1));
					if (neighbor != null)
						soFar.add(neighbor);
				} else /* Left Hand Corner */
				{
					if (temp.leftBottom() != null)
						soFar.add(temp.leftBottom());
					if (temp.bottomLeft() != null)
						soFar.add(temp.bottomLeft());
				}
			}
		}

		else if (yset == true) /*
								 * The point is along the left/right side
								 */
		{
			if (delX < 0)
				nextX = x = temp.x(); /* left side */
			else
				nextX = x = temp.x() + temp.width() + 1; /* right side */
		} else if (xset == true) /*
								 * The point is along the top/bottom edge
								 */
		{
			if (delY < 0)
				nextY = y = temp.y(); /* bottom */
			else
				nextY = y = temp.y() + temp.height() + 1; /* top */
		} else /* Problem... */
		{
			throw new RuntimeException(
					"find_all_tiles_along_line: can't find anything!");
		}
		return findAllTilesAlongLine(temp, new Position(nextX, nextY), selector,
				soFar); // (temp, nextX, nextY, delX, delY, soFar));
	}
	
	private static Tile firstNoncontiguousFullTile(List<Tile> tileList) {
		boolean returnNextFullTile = false;
		while (tileList.size() > 0) {
			Tile tl = tileList.remove(0);
			if (returnNextFullTile == true && tl.isSolid()) {
				return tl;
			} else if (!tl.isSolid() && tileList.size() > 0) {
				returnNextFullTile = true;
			}
		}
		return null;
	}
	
	private static Tile angledTileHelp(Tile currentTile, int anchX, int anchY, SideSelector selector,
			Position pivot, int sizeX, int sizeY, ITileContent box, Tile cornerTile) {
		int epsilon, b, currentX, maxX, minX;
		int orgX = 0, orgY = 0, tempOrgX, tempOrgY;
		int x, y;
		boolean foundOne = false;

		/* This section of code locates the closest, viable origin for <new_>: */

		/* Operate on the left and right 90 degree arcs: */
		if (selector.xSideCount != 0
				&& Math.abs(selector.xSideCount) > Math
						.abs(selector.ySideCount)) { /*
													 * Given a useful delta-X
													 * value, move along the
													 * X-Axis:
													 */

			/*
			 * Now if there is no such tile, reset corner based on the edge of
			 * the known universe:
			 */
			if (cornerTile != null) {
				/*
				 * There is a tile <cornerTile> lying along the line that may
				 * interfere:
				 */
				if (selector.xSideCount > 0) { /* Moving to the right: */
					minX = anchX;
					y = (int) ((float) selector.ySideCount
							/ (float) selector.xSideCount * (cornerTile.x() - anchX))
							+ anchY;

					if (selector.ySideCount == 0)
						maxX = cornerTile.x();

					 /*
					 * either maxX = corner.x_pos or @ y = corner.y_pos
					 */
					else if (selector.ySideCount > 0) {
						/* Moving up and to the right: */
						if (y < cornerTile.y()) {
							/*
							 * intersection occurs along
							 * bottom edge of <cornerTile>
							 */
							maxX = (int) ((float) selector.xSideCount
									/ (float) selector.ySideCount * (cornerTile.y() - anchY))
									+ anchX;
						} else {
							/*
							 * intersection occurs along left edge of
							 * <cornerTile>
							 */
							maxX = cornerTile.x();
						}
					} else {
						/*
						 * either maxX = corner.x_pos or @ y = corner.y_pos
						 * + corner.y_len
						 */
						/* Moving down and to the right: */
						if (y > cornerTile.bottom()) {
							/*
							 * intersection occurs along top edge of
							 * <cornerTile>
							 */
							maxX = (int) ((float) selector.xSideCount
									/ (float) selector.ySideCount * (cornerTile.bottom() - anchY))
									+ anchX;
						} else {
							/*
							 * intersection occurs along left edge of
							 * <cornerTile>
							 */
							maxX = cornerTile.x();
						}
					}
				} else { /* Moving to the left: */
					minX = anchX;
					y = (int) ((float) selector.ySideCount
							/ (float) selector.xSideCount * (cornerTile.right() - anchX))
							+ anchY;

					if (selector.ySideCount == 0)
						maxX = cornerTile.x() + cornerTile.width();

					else if (selector.ySideCount > 0) {
						/*
						 * either minX =
						 * corner.x_pos +
						 * corner.x_len or @ y =
						 * corner.y_pos +
						 * corner.y_len
						 */
						/* Moving up and to the left: */
						if (y < cornerTile.bottom()) {
							/*
							 * intersection occurs along bottom edge of
							 * <cornerTile >
							 */
							maxX = (int) ((float) selector.xSideCount
									/ (float) selector.ySideCount * (cornerTile.y() - anchY))
									+ anchX;
						} else { /*
								 * intersection occurs along right edge of
								 * <cornerTile>
								 */
							maxX = cornerTile.x() + cornerTile.width();
						}
					} else {
						/*
						 * either minX = corner.x_pos + corner.x_len or @ y
						 * = corner.y_pos
						 */
						/* Moving down and to the left: */
						if (y > cornerTile.bottom()) {
							/*
							 * intersection occurs along top edge of
							 * <cornerTile>
							 */
							maxX = (int) ((float) selector.xSideCount
									/ (float) selector.ySideCount * (cornerTile.bottom() - anchY))
									+ anchX;
						} else {
							/*
							 * intersection occurs along right edge of
							 * <cornerTile>
							 */
							maxX = cornerTile.x() + cornerTile.width();
						}
					}
				}
			} else {
				/* cornerTile = null -- The simple case */
				/*
				 * First find the corner tile on the edge of the given space in
				 * the direction that the new_ tile is to be moved:
				 */
				if (selector.xSideCount > 0) {
					/* Moving to the right: */
					cornerTile = currentTile.find_LRHC();
					minX = anchX;
					maxX = cornerTile.right();
				} else {
					/* Moving to the left: */
					cornerTile = currentTile.find_ULHC();
					minX = anchX;
					maxX = cornerTile.x();
				}
			}

			/* Choose a first point to start at */
			epsilon = currentX = (minX + maxX) / 2;
			b = (anchY - (int) ((float) selector.ySideCount
					/ (float) selector.xSideCount * (float) anchX));

			/*
			 * Check the initial points to insure that they fall within the tile
			 * space defined
			 */
			tempOrgX = currentX - pivot.x();
			tempOrgY = (int) (((float) selector.ySideCount / (float) selector.xSideCount) * (float) currentX)
					+ b - pivot.y();
			if (currentTile.locate(tempOrgX, tempOrgY) == null) { /* This is a problem */
				epsilon = currentX = currentX / 2; /* A guess. */
				System.err
						.println("Bad origin point selected; trying again...");

			}

			/*
			 * Perform a newtonian search (along the X-Axis) to find the closest
			 * point to use:
			 */
			while (Math.abs(epsilon) > 1) {
				/*
				 * define the where <new_>'s origin should go, based on the axis
				 * of motion:
				 */
				tempOrgX = currentX - pivot.x();
				tempOrgY = (int) (((float) selector.ySideCount / (float) selector.xSideCount) * (float) currentX)
						+ b - pivot.y();

				/* See if <new_> can be placed: */
				Tile flag = currentTile.areaSearch(tempOrgX, tempOrgY, sizeX, sizeY);

				if (flag != null) {
					/* The tile can't go here. - try going further away */
					NextMoveResult res = nextMove(minX, maxX, currentX,
							FURTHER, epsilon);
					currentX = res.result;
					minX = res.min;
					maxX = res.max;
					epsilon = res.epsilon;
				} else {
					/* The tile can go here - try going closer */
					NextMoveResult res = nextMove(minX, maxX, currentX, CLOSER,
							epsilon);
					currentX = res.result;
					minX = res.min;
					maxX = res.max;
					epsilon = res.epsilon;
					orgX = tempOrgX;
					orgY = tempOrgY;
					foundOne = true;
				}
			}
		}

		/* Otherwise, operate on the top and bottom 90 degree arcs: */
		else if (selector.ySideCount != 0) { /*
											 * The selector.ySideCount value is
											 * more useful, so use y dimensions:
											 */
			/*
			 * This section of code locates the closest, viable origin for
			 * <new_>:
			 */
			if (cornerTile != null) {
				if (selector.ySideCount > 0) { /* Moving Up: */
					minX = anchY;
					x = (int) ((float) selector.xSideCount
							/ (float) selector.ySideCount * (cornerTile.y() - anchY))
							+ anchX;

					if (selector.xSideCount == 0)
						maxX = cornerTile.y();

					else if (selector.xSideCount > 0) {
						/* either maxX = corner.y_pos or @ x = corner.x_pos */
						/* Moving up and to the right: */
						if (x > cornerTile.x()) {
							/* intersection occurs along bottom edge of <cornerTile> */
							maxX = cornerTile.y();
						} else {
							/* intersection occurs along left edge of <cornerTile> */
							maxX = (int) ((float) selector.ySideCount
									/ (float) selector.xSideCount * (cornerTile.x() - anchX))
									+ anchY;
						}
					} else {
						 /* either maxX = corner.y_pos or @ x = corner.x_pos + corner.x_len */
						/* Moving up and to the left: */
						if (x > cornerTile.right()) {
							/* intersection occurs along right edge of <cornerTile> */
							maxX = (int) ((float) selector.ySideCount
									/ (float) selector.xSideCount * (cornerTile.right() - anchX))
									+ anchY;
						} else {
							/* intersection occurs along bottom edge of <cornerTile> */
							maxX = cornerTile.y();
						}
					}
				} else { /* Moving Down: (selector.ySideCount < 0) */
					minX = anchY;
					x = (int) ((float) selector.xSideCount
							/ (float) selector.ySideCount * (cornerTile.bottom() - anchY))
							+ anchX;

					if (selector.xSideCount == 0)
						maxX = cornerTile.bottom();

					else if (selector.xSideCount > 0) {
						/* either minY = corner.y_pos + corner.y_len or @ x=corner.x_pos */
						/* Moving down and to the right: */
						if (x > cornerTile.x()) {
							/*intersection occurs along top edge of <cornerTile> */
							maxX = cornerTile.bottom();
						} else {
							/* intersection occurs along left edge of <cornerTile> */
							maxX = (int) ((float) selector.ySideCount
									/ (float) selector.xSideCount * (cornerTile.x() - anchX))
									+ anchY;
						}
					} else {
						 /*
						 * either minY = corner.y_pos + corner.y_len or @ x
						 * = corner.x_pos
						 */
						if (x > cornerTile.bottom()) {
							/* intersection occurs along right edge of <cornerTile> */
							maxX = (int) ((float) selector.ySideCount
									/ (float) selector.xSideCount * (cornerTile.right() - anchX))
									+ anchY;
						} else {
							/*
							 * intersection occurs along top edge of
							 * <cornerTile>
							 */
							maxX = cornerTile.bottom();
						}
					}
				}
			} else {
				/* cornerTile == null -- The simple case: */
				/*
				 * First find the corner tile on the edge of the given space in
				 * the direction that the new_ tile is to be moved:
				 */
				if (selector.ySideCount > 0) { /* Moving Up: */
					cornerTile = currentTile.find_ULHC();
					minX = anchY;
					maxX = cornerTile.bottom();
				} else { /* Moving Down: */
					cornerTile = currentTile.find_LRHC();
					maxX = cornerTile.y();
					minX = anchY;
				}
			}

			/* Choose a first point to start at */
			epsilon = currentX = (minX + maxX) / 2;
			b = (anchX - (int) (((float) selector.xSideCount / (float) selector.ySideCount) * (float) anchY));

			/*
			 * Check the initial points to insure that they fall within the tile
			 * space defined
			 */
			tempOrgY = currentX - pivot.y();
			tempOrgX = (int) (((float) selector.xSideCount / (float) selector.ySideCount) * (float) currentX)
					+ b - pivot.x();
			if (currentTile.locate(tempOrgX, tempOrgY) == null) /* This is a problem */
			{
				currentTile.locate(tempOrgX, tempOrgY);
				epsilon = currentX = currentX / 2; /* A guess. */
				System.err
						.println("Bad origin point selected; trying again...\n");

			}

			/*
			 * Perform a newtonian search (along the Y-Axis) to find the closest
			 * point to use: Note that <currentX>, <maxX>, & <minX> are now
			 * misnamed.
			 */
			while (Math.abs(epsilon) > 1) {
				/*
				 * define the where <new_>'s origin should go, based on the axis
				 * of motion:
				 */
				tempOrgY = currentX - pivot.y();
				tempOrgX = (int) (((float) selector.xSideCount / (float) selector.ySideCount) * (float) currentX)
						+ b - pivot.x();

				/* See if <new_> can be placed: */
				Tile flag = currentTile.areaSearch(tempOrgX, tempOrgY, sizeX, sizeY);

				if (flag != null) { /*
									 * The tile can't go here. - try going
									 * further away
									 */
					NextMoveResult res = nextMove(minX, maxX, currentX,
							FURTHER, epsilon);
					currentX = res.result;
					minX = res.min;
					maxX = res.max;
					epsilon = res.epsilon;
				} else { /* The tile can go here - try going closer */
					NextMoveResult res = nextMove(minX, maxX, currentX, CLOSER,
							epsilon);
					currentX = res.result;
					minX = res.min;
					maxX = res.max;
					epsilon = res.epsilon;
					orgX = tempOrgX;
					orgY = tempOrgY;
					foundOne = true;
				}
			}
		} else {
			System.err
					.println("angled_tile_help: null <selector.ySideCount>, <selector.xSideCount> values given.\n");
		}

		/*
		 * Given a corner point where to insert the new_ area, adding it to the
		 * new_ space:
		 */
		if (!foundOne)
			return null;
		
		return currentTile.insertTile(orgX, orgY, sizeX, sizeY, box);
	}
	
	private static class NextMoveResult {
		int epsilon;
		int max;
		int min;
		int result;
		public NextMoveResult(int min, int max, int epsilon) {
			this.epsilon = epsilon;
			this.max = max;
			this.min = min;
		}
	}
	
	private static NextMoveResult nextMove(int min, int max, int current,
			int direction, int epsilon) {
		/*
		 * return the new value of current, if a newtonian search step is taken
		 * in the direction of <del>. <epsilon is reset to reflect the move.
		 */
		NextMoveResult result = new NextMoveResult(min, max, epsilon);
		if (direction == FURTHER) {
			/* Move in the direction of <max> */
			/* roundoff bias */
			result.epsilon = (epsilon == 1) ? 0 : (max - current + 1) / 2;
			result.min = current;
			result.result = min + epsilon;
		} else { /* (direction == CLOSER) */
			/* Move in the direction of <min> */
			result.epsilon = (epsilon == 1) ? 0 : (current - min + 1) / 2;
			result.max = current;
			result.result = max - epsilon;
		}
		return result;
	}
	
	
}
